﻿//Copyright (c) 2010 Christopher E. S. King (http://chriskingconsulting.com)
//
//Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files 
// (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, 
// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do 
// so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE 
// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

using System;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Collections;
using System.Collections.Concurrent;
using System.Threading;
using System.Threading.Tasks;
using System.Diagnostics.Contracts;
using System.Reflection;

using King.Extensions;
using King.Reflection;
using System.Text;
using System.Dynamic;

namespace King.Text {

    public sealed class TextNodeLoadException : Exception {
        internal TextNodeLoadException(string message)
            : base(message) {
        }
    }
    public sealed class TextNodeRuntimeException : Exception {
        internal TextNodeRuntimeException(string message)
            : base(message) {
        }
    }

    // Loader caches information about TextNodes to optimize generator performance. For example, when a TextNode 
    // is return as a child each parent TextNode has an oppertunity to override that TextNodes default implementation 
    // of Children by overriding its overload of Children that accepts a value. Caching whether or not a TextNode has 
    // overriden that method and avoid calling all together when no override is provided.
    internal static class TextNodeLoader {
        static TextNodeLoader() {
            TextNodeInfo = GetInfo(typeof(TextNode));
        }
        private static TextNodeInfo TextNodeInfo;
        private static Dictionary<Type, TextNodeInfo> m_infos;
        internal static TextNodeInfo GetInfo(object target) {
            Contract.Ensures(target != null);

            // return the vacuous TextNodeInfo for all internal nodes which are not derivations of TextNode
            if (!(target is TextNode))
                return TextNodeInfo;

            return GetInfo(target.GetType());
        }
        internal static TextNodeInfo GetInfo(Type type) {
            if (m_infos == null)
                m_infos = new Dictionary<Type, TextNodeInfo>();

            TextNodeInfo result;
            if (!m_infos.TryGetValue(type, out result))
                m_infos[type] = result = new TextNodeInfo(type);
            return result;
        }
    }
    internal sealed class TextNodeInfo {

        internal static bool IsPrimitive(object value) {
            var type = value.GetType();
            return type != typeof(string) && !type.IsSubclassOfOrIs<TextNode>() && !typeof(IEnumerable).IsAssignableFrom(type);
        }
        internal static bool IsFlattenLeaf(object value) {
            var type = value.GetType();
            return type == typeof(string) || type.IsSubclassOfOrIs<TextNode>() || !typeof(IEnumerable).IsAssignableFrom(type);
        }

        private Type m_type;
        
        private bool m_overridesEscape, m_overridesSubstitute, m_overridesContent, m_overridesMarkupContent;
        private bool m_containsContent, m_hasSideEffect, m_containsState;
        
        private Type m_markupType;
        private bool m_isEndMarkup;
        
        private Type[] m_substituteTargets;
        private HashSet<char> m_escapeTargets;

        internal TextNodeInfo(Type type) {

            m_type = type;
            m_containsContent = type.IsDefined<TextNodeContainsContentAttribute>();
            m_hasSideEffect = type.IsDefined<TextNodeHasSideEffectAttribute>();
            m_overridesEscape = type.Overrides("Escape", typeof(TextNodeContext), typeof(char));
            m_overridesSubstitute = type.Overrides("Substitute", typeof(TextNodeContext), typeof(object));
            m_overridesContent = type.Overrides("Content");
            m_overridesMarkupContent = type.Overrides("MarkupContent");
            m_markupType = type.ToLinkList(o => o.BaseType).LastOrDefault(o => o.IsDefined<TextNodeMarkupAttribute>());
            m_isEndMarkup = type.IsDefined<TextNodeEndMarkupAttribute>();
            m_containsState = type.IsDeclared<TextNodeContainsStateAttribute>();

            if (m_containsState && !(m_overridesContent || m_containsContent))
                throw LoadException("TextNodeContainsStateAttribute applied " +
                    "without overriding Content or applying TextNodeContainsContentAttribute.");

            var overridesProlog = type.Overrides("Prolog", typeof(TextNodeContext));
            var overridesEpilog = type.Overrides("Epilog", typeof(TextNodeContext));
            if (m_containsState && !(overridesProlog && overridesEpilog))
                throw LoadException("TextNodeContainsStateAttribute is applied but Prolog() and Epilog() are not both overridden.");

            // require TextNodeMarkupAttribute if MarkupContent() is overridden
            if (m_overridesMarkupContent && m_markupType == null)
                throw LoadException("MarkupContent() is overridden but TextNodeMarkupAttribute is not applied.");

            // require TextNodeMarkupAttribute if MarkupContent() is overridden
            if (!m_type.IsAbstract && !m_overridesContent && !m_containsContent)
                throw LoadException("TextNode must override Content() or be attributed with TextNodeMarkupAttribute.");

            // overriding content also overrides inherited applications of TextNodeContainsContentAttribute
            //if (m_containsContent && m_overridesContent)
            //    m_containsContent = false;

            // get substitute targets
            var substituteTargets = type.GetAttribute<TextNodeSubstituteTargetsAttribute>();
            if (substituteTargets != null && !m_overridesSubstitute)
                throw LoadException("TextNodeSubstituteTargetAttribute is applied but Substitute() is not overridden.");

            m_substituteTargets = new[] { typeof(object) };
            if (substituteTargets != null)
                m_substituteTargets = substituteTargets.Types();

            // get escape targets
            var escapeTargets = type.GetAttribute<TextNodeEscapeTargetsAttribute>();
            if (escapeTargets != null && !m_overridesEscape)
                throw LoadException("TextNodeEscapeTargetAttribute is applied but Escape() is not overridden.");

            if (escapeTargets != null)
                m_escapeTargets = escapeTargets.Characters().ToHashSet();
        }
        private TextNodeLoadException LoadException(string message) {
            return new TextNodeLoadException("Failed to load '" + Type.AssemblyQualifiedName + "' because " + message);
        }

        internal Type MarkupType {
            get { return m_markupType; }
        }
        internal bool IsMarkup {
            get { return m_markupType != null; }
        }
        internal bool IsEndMarkup {
            get { return m_isEndMarkup; }
        }
        internal bool OverridesEscape {
            get { return m_overridesEscape; }
        }
        internal bool OverridesSubstitute {
            get { return m_overridesSubstitute; }
        }
        internal bool MaySubstitute(Type type) {
            Contract.Assert(m_overridesSubstitute);
            return m_substituteTargets.Any(o => o.IsAssignableFrom(type));
        }
        internal bool ContainsState {
            get { return m_containsState; }
        }
        internal bool ContainsContent {
            get { return m_containsContent; }
        }
        internal bool HasSideEffect {
            get { return m_hasSideEffect; }
        }
        internal bool OverridesContent {
            get { return m_overridesContent; }
        }
        internal bool IsEscapeTarget(char character) {
            Contract.Assert(m_overridesEscape);
            if (m_escapeTargets == null)
                return true;
            return m_escapeTargets.Contains(character);
        }
        internal Type Type {
            get { return m_type; }
        }
    }

    // State required by Frame to lazily generate the "children" of a string. In the common case the children 
    // of a string are simply its characters. But there are two special cases. First, each character can be 
    // escaped by parent TextNodes who've overriden Escape(). Second, StringStartLine is returned as
    // a child of a string in two cases. First, before the first character returned during traversal 
    // of the tree. Second, before the first character returned after a new line. See TextGeneratorState.
    internal class TextNodeFrameState {

        private string m_escapedCharacter;
        private int m_escapedCharacterIndex;
        private bool NextEscapedCharacter(out char leaf) {
            leaf = default(char);

            if (m_escapedCharacter.Length == m_escapedCharacterIndex) {
                m_escapedCharacterIndex = 0;
                m_escapedCharacter = null;
                return false;
            }

            leaf = m_escapedCharacter[m_escapedCharacterIndex++];
            return true;
        }

        private int m_stringIndex;
        private bool NextCharacter(TextNodeFrame frame, string value, out char leaf) {
            leaf = default(char);

            if (m_escapedCharacter != null && NextEscapedCharacter(out leaf))
                return true;

            do {
                if (value.Length == m_stringIndex)
                    return false;

                leaf = value[m_stringIndex++];
                m_escapedCharacter = frame.EscapeLink == null ? null : frame.EscapeLink.Escape(frame.Runtime, leaf);
                if (m_escapedCharacter == null)
                    return true;

            } while (string.Empty.Equals(m_escapedCharacter));

            return NextEscapedCharacter(out leaf);
        }

        private char? m_nextCharacterAfterStartLine;
        internal bool NextCharacterOrStartLine(TextGenerator generator, TextNodeFrame frame, out char leaf, out object internalNode) {
            leaf = default(char);
            internalNode = null;
            var value = (string)frame.Value;

            // if testing a sub-tree to see if it contains characters then there 
            // is no need to actually return the character just that there is one.
            if (generator.State.ContentTraversal)
                return string.Empty != value;

            // pull the next character from the stream or if last character was deferred in order
            // to return a StringStartLine then go ahead and return that deferred character now
            if (m_nextCharacterAfterStartLine != null) {
                leaf = (char)m_nextCharacterAfterStartLine;
                m_nextCharacterAfterStartLine = null;
            } else if (!NextCharacter(frame, value, out leaf))
                return false;

            // ask the generator if this is the first in a new line of text and
            // if so then return a StringStartLine and defer returning this character
            if (generator.State.NextStartLine(out internalNode)) {
                m_nextCharacterAfterStartLine = leaf;
                leaf = default(char);
            }

            return true;
        }
    }

    internal class TextNodeMarkupLink {

        private TextNodeMarkupLink m_next;
        private Type m_markupType;

        internal TextNodeMarkupLink(TextNodeMarkupLink next, Type markupType) {
            m_next = next;
            m_markupType = markupType;
        }

        internal bool IsMarkupRoot(Type markupType) {
            return this.ToLinkList(o => o.m_next).None(o => o.m_markupType == markupType);
        }
        internal IEnumerable<Type> EnclosingScopes(Type markupType) {
            return MarkupTypes().SkipWhile(o => o != markupType).Skip(1);
        }
        internal IEnumerable<Type> MarkupTypes() {
            return this.ToLinkList(o => o.m_next, o => o.m_markupType);
        }
    }
    internal class TextNodeEscapeLink {

        private TextNodeEscapeLink m_next;
        private TextNode m_value;
        private TextNodeInfo m_info;
        private int m_height;

        internal TextNodeEscapeLink(TextNodeEscapeLink next, int height, object value) {
            m_next = next;
            m_height = height;
            m_value = (TextNode)value;
            m_info = TextNodeLoader.GetInfo(value);
        }

        private bool ShouldEscape(TextGenerator generator, TextNodeContext context, char character) {

            // most common case is that the character does not need to be escaped
            if (!m_info.IsEscapeTarget(character))
                return false;

            // this escaper is not marked as markup so it is active all the time
            if (!m_info.IsMarkup)
                return true;

            // do not escape past Evaluate() frames
            if (generator.State.IsMarkupTypeDisabled(m_info.MarkupType))
                return false;

            // markup escapers are active only when the are the deepest escaper of their type
            if (context.Descendents(m_info.MarkupType).Any())
                return false;

            // markup escapers do not escape enclosing markup characters
            var enclosingMarkupTypes = generator.Stack.Peek().MarkupLink.EnclosingScopes(m_info.MarkupType);
            var enclosingEscapers = enclosingMarkupTypes.Select(e => generator.Stack.FirstOrDefault(o => o.Info.MarkupType == e));
            if (enclosingEscapers.WhereNotDefault().Any(o => !o.Info.IsEndMarkup))
                return false;

            return true;
        }

        internal string Escape(TextGenerator generator, char character) {

            string result = null;

            var context = new TextNodeContext(generator, m_height);
            if (ShouldEscape(generator, context, character))
                result = m_value.Escape(context, character);

            // there are no more escapers
            if (m_next == null)
                return result;

            // the case where this escaper did not escape this character but other parent escapers exist
            if (result == null)
                return m_next.Escape(generator, character);

            // the most difficult case when the char is escaped more than once  (e.g. xml in xml)
            var nextEscape = m_next;
            return result.Select(o => nextEscape.Escape(generator, o) ?? o.ToString())
                .Aggregate(string.Empty, (a, s) => a + s);
        }
    }
    internal class TextNodeSubstituteLink {
        
        private TextNodeSubstituteLink m_next;
        private int m_height;
        private TextNode m_value;
        private TextNodeInfo m_info;

        internal TextNodeSubstituteLink(TextNodeSubstituteLink next, int height, object value, TextNodeInfo info) {
            m_next = next;
            m_height = height;
            m_value = (TextNode)value;
            m_info = info;
        }

        internal IEnumerable<object> Substitute(TextGenerator generator, object value) {
            if (m_info.MaySubstitute(value.GetType())) {
                var result = m_value.Substitute(new TextNodeContext(generator, m_height, true), value);
                if (result != null)
                    return result;
            }

            if (m_next != null)
                return m_next.Substitute(generator, value);

            return null;
        }
        internal TextNodeSubstituteLink Next {
            get { return m_next; }
        }
    }

    /// <summary>
    /// The context of the current post-order traversal relative to the TextNode into which its passed. It holds the
    /// location (the height) of the TextNode on the stack. Given this it can return the ancestors and descendents 
    /// relative to the TextNode. This struct should not be copied onto the heap because it holds state that is only 
    /// valid during the method call. 
    /// </summary>
    public struct TextNodeContext {
        private TextGenerator m_generator;
        private int m_height;
        private bool m_inSubstitute;

        internal TextNodeContext(TextGenerator generator, int height, bool inSubstitute = false) {
            m_generator = generator;
            m_height = height;
            m_inSubstitute = inSubstitute;
        }

        /// <summary>
        /// Provides access to the parent TextNodes of the TextNode into which this context is passed.
        /// </summary>
        /// <param name="type">Filter only TextNodes assignable to this type.</param>
        /// <returns>TextNodes below the current TextNode on the stack in descending order of height on the stack.</returns>
        public IEnumerable<object> Ancestors(Type type) {
            return m_generator.Stack[type].Ancestors(m_height);
        }
        /// <summary>
        /// Provides access to the parent TextNodes of the TextNode into which this context is passed.
        /// </summary>
        /// <typeparam name="T">Filter only TextNodes assignable to this type.</typeparam>
        /// <returns>TextNodes below the current TextNode on the stack in descending order of height on the stack.</returns>
        public IEnumerable<T> Ancestors<T>() {
            return Ancestors(typeof(T)).Cast<T>();
        }
        /// <summary>
        /// Provides access to the parent TextNodes of the TextNode into which this context is passed.
        /// </summary>
        /// <returns>TextNodes below the current stream node on the stack in descending order of height on the stack.</returns>
        public IEnumerable<object> Ancestors() {
            return Ancestors(typeof(object));
        }

        /// <summary>
        /// Provides access to descendents of the TextNode into which this context is passed ending with the TextNode currently
        /// being visted by the traversal.
        /// </summary>
        /// <param name="type">Filter only TextNodes assignable to this type.</param>
        /// <returns>TextNodes above the current TextNode on the stack in ascending order of height on the stack.</returns>
        public IEnumerable<object> Descendents(Type type) {
            return m_generator.Stack[type].Descendents(m_height);
        }
        /// <summary>
        /// Provides access to descendents of the TextNode into which this context is passed ending with the TextNode currently
        /// being visted by the traversal.
        /// </summary>
        /// <typeparam name="T">Filter only TextNodes assignable to this type.</typeparam>
        /// <returns>TextNodes above the current TextNode on the stack in ascending order of height on the stack.</returns>
        public IEnumerable<T> Descendents<T>() {
            return Descendents(typeof(T)).Cast<T>();
        }
        /// <summary>
        /// Provides access to descendents of the TextNode into which this context is passed ending with the TextNode currently
        /// being visted by the traversal.
        /// </summary>
        /// <returns>TextNodes above the current TextNode on the stack in ascending order of height on the stack.</returns>
        public IEnumerable<object> Descendents() {
            return Descendents(typeof(object));
        }

        /// <summary>
        /// Similar to UNIX forking of a process Fork() creates a TextNodeTask which contains a clone of the current execution 
        /// stack and enqueue it on the current TextGenerator for asynchronos retrieval via TextGenerator.NextTask(). 
        /// </summary>
        /// <param name="root">The root of the new Forked execution stack. Traversal will end with this root is popped off 
        /// the stack. The original stack is only used to provide context.</param>
        public void Fork(params object[] root) {
            m_generator.Fork(root);
        }

        public T GetValue<T>(object key, object initialValue = null) {
            return (T)GetValue(key, initialValue);
        }
        public object GetValue(object key, object initialValue = null) {
            Contract.Requires(key != null);

            object result;
            if (!TryGetValue(key, out result)) {
                if (initialValue == null)
                    throw new TextNodeRuntimeException("Key not found.");
                SetValue(key, initialValue);
                result = initialValue;
            }
            return result;
        }
        public bool TryGetValue(object key, out object result) {
            Contract.Requires(key != null);
            
            return m_generator.State.TryGetValue(m_height, key, out result);
        }
        public void SetValue(object key, object value) {
            Contract.Requires(key != null);
            Contract.Requires(value == null || value is string || value is decimal || value.GetType().IsPrimitive);

            m_generator.State.SetValue(m_height, key, value);
        }

        /// <summary>
        /// Ask ancestors of the TextNode into which the context was passed to substitute the value. 
        /// </summary>
        /// <param name="value">The value to substitute.</param>
        /// <returns>The subtituted value. Return null if no ancestors substituted a value.</returns>
        public IEnumerable<object> Substitute(object value) {
            if (value == null)
                return null;

            var height = m_inSubstitute ? m_height : m_generator.Stack.Height;

            var substituteLink = m_generator.Stack.Peek(height).SubtituteLink;

            if (substituteLink == null)
                return null;

            return substituteLink.Substitute(m_generator, value);
        }

        /// <summary>
        /// Flatten traverses the tree rooted at value traversing through all nodes 
        /// implementing IEnumerable until a TextNodes or primitive type is found.
        /// For example, new object[] { 1, new[] { 2 }, 3 } => 1, 2, 3.
        /// </summary>
        public IEnumerable<object> Flatten(params object[] value) {
            return m_generator.Traversal.Flatten(value);
        }

        /// <summary>
        /// Look ahead in the stream to tests if there are any characters in the tree rooted at value. 
        /// </summary>
        public bool ContainsContent(params object[] value) {
            if (value == null)
                return false;

            return m_generator.Traversal.ContainsContent(value);
        }

        /// <summary>
        /// Returns true if the value evaluated in the current context contains a new line sequence.
        /// Push TextDisableMarkup before the value is traversed to indicate to nodes doing markup
        /// they should disable emitting markup.
        /// </summary>
        public bool ContainsNewLine(params object[] value) {
            var generator = m_generator;
            bool containsNewLine = false;
            Evaluate(value, delegate(char character) {
                return (containsNewLine = generator.State.AtEndOfNewLine) == false;
            });
            return containsNewLine;
        }

        /// <summary>
        /// Traverse the tree rooted at value in the current context with markup disabled calling
        /// back to visitor for every character encountered.
        /// </summary>
        public void Evaluate(object value, Func<char, bool> visitor) {
            Contract.Requires(visitor != null);

            if (value == null)
                return;

            m_generator.Traversal.Evaluate(value, visitor);
        }

        /// <summary>
        /// Traverse the tree rooted at value in the current context with markup disabled.
        /// </summary>
        public string Evaluate(object value) {
            if (value == null)
                return null;

            var stringBuilder = new StringBuilder();
            Evaluate(value, delegate(char character) { 
                stringBuilder.Append(character); 
                return true; 
            });
            return stringBuilder.ToString();
        }
    }

    // Every child returned during the post-order traversal that is an internal node is wrapped in a Frame 
    // before being pushed onto the stack. Frame abstracts the differences in how children are enumerated 
    // (see NextChild) and encapsulates all logic required in general to generate children and so maintains
    // all state required to generate the next child. 
    // Frame also gives parents, moving from yougest to oldest, (or deepest to shallowest on the stack) are given an
    // oppertunity to substitute one child for another (stopping after the first substitution) and to escape the 
    // character ouput stream (with older parents possibly escaping the escape stream of younger parents ultimately 
    // starting with a single character leaf).
    internal sealed class TextNodeFrame {

        private static readonly IEnumerator<object> EmptyEnumerator = Enumerable.Empty<object>().GetEnumerator();

        private TextGenerator m_generator;
        private int m_height;
        private object m_value;
        private TextNodeInfo m_info;
        private TextNodeFrameState m_state;
        private TextNodeSubstituteLink m_substituteLink;
        private TextNodeEscapeLink m_escapeLink;
        private TextNodeMarkupLink m_markupLink;

        // streamNode and IEnumerable nodes generate their child with an enumerator which is stored here
        private IEnumerator<object> m_enumerator;

        internal TextNodeFrame(TextGenerator generator, TextNodeFrame parent, int height, object value) {
            Contract.Ensures(value != null);
            Contract.Ensures(!(value is TextNodeTask));
            Contract.Ensures(!value.GetType().IsPrimitive || value is bool);

            m_generator = generator;
            m_height = height;
            m_value = value;
            m_info = TextNodeLoader.GetInfo(value);
            m_state = new TextNodeFrameState();

            if (parent != null) {
                m_substituteLink = parent.m_substituteLink;
                m_escapeLink = parent.m_escapeLink;
                m_markupLink = parent.m_markupLink;
            }

            var markupType = m_info.MarkupType;
            if (markupType != null && (m_markupLink == null || m_markupLink.IsMarkupRoot(markupType)))
                m_markupLink = new TextNodeMarkupLink(m_markupLink, markupType);

            if (m_info.OverridesSubstitute)
                m_substituteLink = new TextNodeSubstituteLink(m_substituteLink, m_height, m_value, m_info);

            if (m_info.OverridesEscape)
                m_escapeLink = new TextNodeEscapeLink(m_escapeLink, m_height, m_value);
        }

        // TextNode.Children() forces implementers to return an IEnumerable<object> even when they only
        // need to return a single child. To mitigate this, optimize the case when Children() returns an array
        // with a single element. If value is an array with one element then return that element else null.
        private bool NextChildIfEmptyOrSingleElementArray(out object child) {
            child = null;

            var array = m_value as Array;
            if (array != null) {

                if (array.Length == 0)
                    return true;

                if (array.Length == 1) {
                    child = array.GetValue(0);
                    return true;
                }
            }

            return false;
        }

        // yield the next child in the general case where this frame is not a string. There are two cases: (1) TextNodes 
        // provide an epxlicit function to get their children -- TextNode.Children(). (2) IEnumerables are assumed
        // to provide their children through enumeration. If that assumption is wrong than values of that type can be 
        // substituted before reaching this logic by a parent via TextNode.Substitute().
        private object NextChild(TextGenerator generator) {

            // generator for an enumerator is an enumerable
            if (m_enumerator == null) {

                // while looking for an enumerator it may be discovered there is only a single child
                // which is returned immediately so provide an empty enumerator by default.
                m_enumerator = EmptyEnumerator;

                IEnumerable<object> enumerable = null;

                // Optimize for the case of an empty array or an array with a single element 
                object singleton;
                if (NextChildIfEmptyOrSingleElementArray(out singleton))
                    return singleton;

                // If value is a streamNode than ask it to return its children
                var streamNode = m_value as TextNode;
                if (streamNode != null) {
                    var state = generator.State;

                    // prevent traversing a node with side effects more than once by disallowing content and Evaluate traversals
                    if (m_info.HasSideEffect && state.EvaluateTraversal)
                        throw new TextNodeRuntimeException(
                            "Cannot preform a Evaluate of node '" + m_info.Type.AssemblyQualifiedName +
                            "' because the node is attributed with " + typeof(TextNodeHasSideEffectAttribute).Name + ".");

                    var context = new TextNodeContext(m_generator, m_height);

                    if (state.ContentTraversal) {
                        // allow streamNodes to strip "wrapping" and only return nodes deemed to determine content.
                        enumerable = streamNode.Content();

                    } else {
                        enumerable = streamNode.Children(context);
                    }

                    if (enumerable == null)
                        enumerable = Enumerable.Empty<object>();
                }

                // TextNode.Children() (or TextNode.Content()) could return a subclass of TextNode 
                // which implements IEnumerable in which case it must be pushed onto the stack to 
                // provide context before enumerating its children 
                if (enumerable is TextNode)
                    return enumerable;

                // If object is IEnumerable then evaluate it to get the children
                if (enumerable == null && m_value is IEnumerable)
                    enumerable = ((IEnumerable)m_value).Cast<object>();

                // Can't figure out how to enumerate children so throw an exception
                if (enumerable == null)
                    throw new ArgumentException(
                        "Cannot figure out how to get children for an instance of type: " + m_value.GetType().AssemblyQualifiedName);

                m_enumerator = enumerable.GetEnumerator();
            }

            // return all non-null elements out of the enumerable
            while (m_enumerator.MoveNext()) {
                var current = m_enumerator.Current;
                if (current == null)
                    continue;

                return current;
            }

            // enumeration complete
            return null;
        }

        // yield the next child of this frame. A child will either be a character in which case it is a leaf or a
        // Frame in which case it is pushed back on the stack so its children can be enumerated. There are three
        // special cases: (1) TextGenerator, (2) IsEmpty traversals, and (3) Flatten traversals (see code).
        internal TextNodeChildType NextChild(
            TextGenerator generator, out char childCharacter, out object child) {

            childCharacter = default(char);
            child = null;

            var textNode = Value as TextNode;
            if (generator.State.ContentTraversal) {

                // short circut content traversal if the TextNode is attributed to indicate it always has content.
                if (m_info.ContainsContent) 
                    return TextNodeChildType.Leaf;

                // short circut content traversal if the TextNode has been previously determined to have content.
                if (textNode != null && textNode.HasContent)
                    return TextNodeChildType.Leaf;
            }

            if (m_value is string) {

                // return false if every character has been enumerated
                if (!State.NextCharacterOrStartLine(generator, this, out childCharacter, out child))
                    return TextNodeChildType.End;

                // return a leaf child aka a character
                if (child == null)
                    return TextNodeChildType.Leaf;

                // the start of a new line has been encountered while traversing the string
                Contract.Assert(child is TextStartLine);

            // if not a string then get the next child of this frame
            } else if ((child = NextChild(generator)) == null)
                return TextNodeChildType.End;

            // when flattening the goal is to remove containers (e.g. linq enumerators, Array, List<T>, etc)
            // and return everything else. this way a set defined by a linq expression could be passed to StringJoin
            if (generator.Traversal.FlatteningTraversal && TextNodeInfo.IsFlattenLeaf(child))
                return TextNodeChildType.Leaf;

            return TextNodeChildType.Internal;
        }
        
        internal object Value {
            get { return m_value; }
        }
        internal TextNodeInfo Info {
            get { return m_info; }
        }
        internal TextGenerator Runtime {
            get { return m_generator; }
        }
        internal TextNodeFrameState State {
            get { return m_state; }
        }
        internal TextNodeEscapeLink EscapeLink {
            get { return m_escapeLink; }
        }
        internal TextNodeSubstituteLink SubtituteLink {
            get { return m_substituteLink; }
        }
        internal TextNodeMarkupLink MarkupLink {
            get { return m_markupLink; }
        }

        public override string ToString() {
            return Value == null ? "(null)" : Value.GetType().Name;
        }
    }

    // Stack contains a stack of TextNodeFrames. This is the stack used to preform the post-order traversal of the tree.
    // Stack also builds a cache that given a type as a key can retreive all values on the stack that can 
    // be cast to that key. This cache is accessable via TextNodeContext which is passed to TextNodes.Children 
    // and in this way the children returned can be a function of its ancestors or descendents.
    internal sealed class TextNodeStack : IEnumerable<TextNodeFrame> {

        private static HashSet<object> s_statefulObjects = new HashSet<object>();

        private TextGenerator m_generator;
        private int m_heightOffset;
        private Stack<TextNodeFrame> m_stack;
        private Dictionary<Type, TextNodeStackByType> m_cache;
        private int m_statefulObjects;

        internal TextNodeStack(TextGenerator generator) {
            m_generator = generator;
            m_stack = new Stack<TextNodeFrame>();
            m_cache = new Dictionary<Type, TextNodeStackByType>();
        }
        private TextNodeStack(TextGenerator generator, TextNodeStack source) {
            m_generator = generator;
            m_cache = new Dictionary<Type, TextNodeStackByType>();
            foreach (var pair in source.m_cache)
                m_cache[pair.Key] = new TextNodeStackByType(pair.Value);

            m_stack = new Stack<TextNodeFrame>();
            m_stack.Push(new TextNodeFrame(generator, source.Peek(), Height, string.Empty));
            m_heightOffset = source.Height + 1;
        }

        private void Cache(TextNodeInfo info, object value) {

            // only derivations of TextNode are stored in the dictionary
            var streamNode = value as TextNode;
            if (streamNode == null)
                return;

            // track stateful objecs globally and locally
            if (info.ContainsState) {

                // stateful objects can only be referenced once from any stack
                if (s_statefulObjects.Contains(value))
                    throw new TextNodeRuntimeException(
                        "A stateful object of type '" + value.GetType().AssemblyQualifiedName +
                        "' is already referenced from this or another stack and so cannot be added to this stack.");
                
                s_statefulObjects.Add(value);
                m_statefulObjects++;
            }

            // cache value by it type and base types
            var type = streamNode.GetType();
            while (type != typeof(object)) {

                // get the nodes of type or subclasses of type
                TextNodeStackByType cache;
                if (!m_cache.TryGetValue(type, out cache))

                    // if this is the first encounter with a value of this type
                    // then create a stack to hold values of this type
                    m_cache[type] = cache = new TextNodeStackByType();

                // cache the value
                cache.Push(Height, streamNode);

                // cache the next base type
                type = type.BaseType;
            }
        }
        private void UnCache(TextNodeInfo info, object value) {
            var type = value.GetType();

            // only derivations of TextNode are stored in the dictionary
            if (!(value is TextNode))
                return;

            // remove stateful object from cache so it can be referenced from another stack
            if (info.ContainsState) {
                var wasCached = s_statefulObjects.Remove(value);
                m_statefulObjects--;
                Contract.Assert(wasCached);
            }

            // uncache this value from its type and all its base types
            while (type != typeof(object)) {

                // uncache this value
                m_cache[type].Pop();

                // uncache from the next base type
                type = type.BaseType;
            }
        }
        
        internal int Height {
            get { return m_stack.Count + m_heightOffset; }
        }
        internal int HeightOffset {
            get { return m_heightOffset; }
        }
        internal TextNodeFrame Peek() {
            var result = m_stack.FirstOrDefault();
            return result;
        }
        internal TextNodeFrame Peek(int depth) {
            var result = m_stack.Skip(m_stack.Count - depth).First();
            return result;
        }
        internal TextNodeFrame Pop() {
            var frame = Peek();

            var textNode = frame.Value as TextNode;
            if (textNode != null)
                textNode.Epilog(new TextNodeContext(m_generator, Height));

            m_stack.Pop();
            UnCache(frame.Info, frame.Value);
            return frame;
        }
        internal int Push(object value) {
            var frame = new TextNodeFrame(m_generator, Peek(), Height, value);

            Cache(frame.Info, value);
            m_stack.Push(frame);
            
            var textNode = value as TextNode;
            if (textNode != null)
                textNode.Prolog(new TextNodeContext(m_generator, Height));
            
            return Height - 1;
        }
        internal TextNodeStackByType this[Type type] {
            get {
                if (type == typeof(object))
                    type = typeof(TextNode);

                TextNodeStackByType cache = null;
                m_cache.TryGetValue(type, out cache);
                return cache ?? TextNodeStackByType.Empty;
            }
        }

        internal TextNodeStack DeepCopy(TextGenerator generator) {
            if (m_statefulObjects > 0)
                throw new TextNodeRuntimeException(
                    "TextGenerator stack contains stateful nodes and cannot be cloned.");

            return new TextNodeStack(generator, this);
        }

        public IEnumerator<TextNodeFrame> GetEnumerator() {
            return m_stack.GetEnumerator();
        }
        IEnumerator IEnumerable.GetEnumerator() {
            return GetEnumerator();
        }
    }
    internal sealed class TextNodeStackByType {
        internal static readonly TextNodeStackByType Empty = new TextNodeStackByType();

        private List<KeyValuePair<int, TextNode>> m_list;

        internal TextNodeStackByType() {
            m_list = new List<KeyValuePair<int, TextNode>>();
        }
        internal TextNodeStackByType(TextNodeStackByType source) {
            m_list = new List<KeyValuePair<int, TextNode>>(source.m_list);
        }

        private int Find(int target, bool firstAbove) {
            if (m_list.Count == 0)
                return firstAbove ? 1 : -1;

            int lower = 0;
            int upper = m_list.Count - 1;
            int index = 0;
            int value = 0;

            do {
                index = lower + (upper - lower) / 2;

                value = m_list[index].Key;

                if (target == value)
                    return index + (firstAbove ? 1 : -1);

                if (value < target)
                    lower = index + 1;
                else
                    upper = index - 1;

            } while (upper >= lower);

            Contract.Assert(index == upper || index == lower);
            Contract.Assert(value != target);

            if (value > target) {
                if (firstAbove)
                    return index;
                
                return index - 1;
            
            } else {
                if (firstAbove)
                    return index + 1;
                
                return index;
            }
        }

        internal void Push(int height, TextNode node) {
            m_list.Add(new KeyValuePair<int, TextNode>(height, node));
        }
        internal TextNode Pop() {
            var lastIndex = m_list.Count - 1;
            var result = m_list[lastIndex];
            m_list.RemoveAt(lastIndex);
            return result.Value;
        }

        internal IEnumerable<TextNode> Ancestors(int height) {
            var index = Find(height, false);

            for (int i = index; i >= 0; i--)
                yield return m_list[i].Value;
        }
        internal IEnumerable<TextNode> Descendents(int height) {
            var index = Find(height, true);

            for (int i = index; i < m_list.Count; i++)
                yield return m_list[i].Value;
        }
    }

    // Traversal contains logic to preform the pre-order traversal of TextNodes. Logic for two other traversals 
    // are also found here. First, FlatteningTraversal "flattens" a provied value by eagerly traversing through any 
    // IEnumerables like linq expressions and arrays to return TextNodes and Primitves as leafs (It's the TextNode 
    // equivalant of Linq .SelectMany()). Second, ContentTraversal evaluates a provided value to test if it yields 
    // any characters if evaluated with the current generator. ContentTraversal traversals calls TextNode.Content() 
    // instead of TextNode.Children() to get the children of a TextNode. Content() must be stateless. 
    internal sealed class TextNodeTraversal {

        private TextGenerator m_generator;
        private bool m_flatteningTraversal;

        internal TextNodeTraversal(TextGenerator textGenerator) {
            m_generator = textGenerator;
        }

        // Do a depth-first post-order traversal of the tree starting with the root frame.
        // Keeping this method simple was a design goal. This goal was achieved by moving the 
        // complex logic for determining when a child was an interal vs a leaf frame into Frame.
        internal IEnumerable<char?> Traverse(object value = null, List<object> result = null) {
            var stack = m_generator.Stack;
            
            int tos = stack.HeightOffset;
            if (value != null) 
                tos = stack.Push(m_generator.Substitute(value));

            while (stack.Height > tos) {
                var frame = stack.Peek();

                while (true) {

                    char childCharacter = default(char);
                    object child = null;

                    var childType = frame.NextChild(m_generator, out childCharacter, out child);

                    // no more children
                    if (childType == TextNodeChildType.End) {
                        var parent = stack.Pop();
                        m_generator.State.RemoveUserState(stack.Height);
                        break;
                    }

                    // internal frame
                    if (childType == TextNodeChildType.Internal) {
                        Contract.Assert(child != null);

                        // substitute child
                        child = m_generator.Substitute(child);

                        // push child frame and continue traversal
                        stack.Push(child);

                        // flush
                        if (child is TextFlush)
                            yield return null;

                        break;

                    // leaf frame
                    } else {
                        Contract.Assert(childType == TextNodeChildType.Leaf);

                        if (m_flatteningTraversal) {
                            Contract.Assert(child != null);
                            result.Add(child);

                        } else {
                            Contract.Assert(child == null);

                            yield return childCharacter;

                            // should have stopped traversal once it is determined that the tree contains a leaf
                            Contract.Assert(!m_generator.State.ContentTraversal);
                        }
                    }
                }
            }
        }

        internal bool FlatteningTraversal {
            get { return m_flatteningTraversal; }
        }
        
        internal IEnumerable<object> Flatten(object value) {
            Contract.Ensures(Contract.OldValue(m_generator.Stack.Height) == m_generator.Stack.Height);

            if (value == null)
                return Enumerable.Empty<object>();
            
            m_flatteningTraversal = true;

            var result = new List<object>();

            Traverse(value, result).GetEnumerator().MoveNext();

            m_flatteningTraversal = false;
            return result;
        }
        internal bool ContainsContent(object value) {
            Contract.Ensures(Contract.OldValue(m_generator.Stack.Height) == m_generator.Stack.Height);
            
            var originalState = m_generator.State;
            m_generator.State = originalState.DeepCopy(contentTraversal: true);
            
            var tos = m_generator.Stack.Height;
            var enumerator = Traverse(value).GetEnumerator();

            bool result = false;
            do { result = enumerator.MoveNext(); } while (result && enumerator.Current == null);

            while (m_generator.Stack.Height > tos) {
                var frameWithContent = m_generator.Stack.Pop();
                var nodeWithContent = frameWithContent.Value as TextNode;
                if (nodeWithContent != null)
                    nodeWithContent.HasContent = true;
            }

            m_generator.State = originalState;
            return result;
        }
        internal void Evaluate(object value, Func<char, bool> visitor) {
            Contract.Assert(value != null);
            Contract.Assert(visitor != null);

            var originalState = m_generator.State;
            m_generator.State = originalState.DeepCopy(evaluateTraversal: true);
            
            var tos = m_generator.Stack.Height;
            var producer = m_generator.GetProducer(value);
            
            foreach (var character in producer) {
                if (character == null)
                    continue;

                if (!visitor((char)character))
                    break;
            }

            while (m_generator.Stack.Height > tos)
                m_generator.Stack.Pop();

            Contract.Assert(m_generator.Stack.Height == tos);

            m_generator.State = originalState;
        }
    }
    internal enum TextNodeChildType {
        End,
        Leaf,
        Internal,
    }

    // A frame needs to know if the previous frame to return characters ended its stream with a new line 
    // in order to determine if a StringStartLine should be injected before returning its first character.
    // to enable this TextGeneratorState is stored in the TextGenerator and every frame
    // reports its characters so that subsequent frames can see if the stream has ended in a new line.
    internal class TextGeneratorState {

        private TextGeneratorState m_next;
        private TextGenerator m_generator;
        private NewLineDetector m_newLineDetector;
        private bool m_isStartLine;
        private bool m_contentTraversal;
        private bool m_evaluateTraversal;
        private HashSet<Type> m_disabledMarkupTypes;
        private Dictionary<int, Dictionary<object, object>> m_userStateByHeight;

        internal TextGeneratorState(TextGenerator generator) {
            m_generator = generator;
            m_isStartLine = true;
            m_newLineDetector = new NewLineDetector();
        }
        private TextGeneratorState(TextGeneratorState source, 
            TextGenerator generator, bool contentTraversal, bool evaluateTraversal) {

            // require only one type of traversal be allowed at a given time
            Contract.Assert(contentTraversal == false || evaluateTraversal == false);

            m_next = source;
            m_generator = generator ?? source.m_generator;
            m_isStartLine = source.m_isStartLine;
            m_newLineDetector = source.m_newLineDetector;
            m_evaluateTraversal = evaluateTraversal;
            m_contentTraversal = contentTraversal;

            m_disabledMarkupTypes = source.m_disabledMarkupTypes;
            if (evaluateTraversal) {
                var markupLink = m_generator.Stack.Peek().MarkupLink;
                if (markupLink != null)
                    m_disabledMarkupTypes = markupLink.MarkupTypes().ToHashSet();
            }
        }

        internal void RemoveUserState(int height) {
            if (m_userStateByHeight != null)
                m_userStateByHeight.Remove(height);
        }
        internal bool TryGetValue(int height, object key, out object value) {
            if (m_userStateByHeight != null) {
                var userState = m_userStateByHeight.GetValueOrDefault(height);
                if (userState != null && userState.TryGetValue(key, out value))
                    return true;
            }

            if (m_next != null) {
                var result = m_next.TryGetValue(height, key, out value);
                if (result)
                    SetValue(height, key, value);
                return result;
            }

            value = null;
            return false;
        }
        internal void SetValue(int height, object key, object value) {
            if (m_userStateByHeight == null)
                m_userStateByHeight = new Dictionary<int, Dictionary<object, object>>();

            var userState = m_userStateByHeight.GetValueOrDefault(height);
            if (userState == null)
                m_userStateByHeight[height] = userState = new Dictionary<object, object>();

            userState[key] = value;
        }

        internal bool AtEndOfNewLine {
            get { return m_newLineDetector.AtEndOfNewLine; }
        }
        internal bool InNewLineSequence {
            get { return m_newLineDetector.InNewLine; }
        }
        internal void OnCharacterReturned(char character) {
            // detect the start of a new line by detecting the end of a new line
            if (m_newLineDetector.Next(character))
                m_isStartLine = true;
        }
        internal bool NextStartLine(out object startLine) {
            startLine = null;
            if (!m_isStartLine)
                return false;

            m_isStartLine = false;
            startLine = TextStartLine.Singleton;
            return true;
        }
        internal bool ContentTraversal {
            get { return m_contentTraversal; }
        }
        internal bool EvaluateTraversal {
            get { return m_evaluateTraversal; }
        }
        internal bool IsMarkupTypeDisabled(Type type) {
            if (m_disabledMarkupTypes == null)
                return false;
            return m_disabledMarkupTypes.Contains(type);
        }

        internal TextGeneratorState DeepCopy(
            TextGenerator generator = null,
            bool contentTraversal = false, 
            bool evaluateTraversal = false) {
            // require exact copies can only be made when not doing a content or evaluate traversal (for tasks)
            Contract.Assert(contentTraversal == true || evaluateTraversal == true || 
                (m_contentTraversal == false && m_evaluateTraversal == false));

            return new TextGeneratorState(this, generator, contentTraversal, evaluateTraversal);
        }
    }

    /// <summary>
    /// The generator holds the execution stack for the depth first post-order traversal of a tree
    /// composed of TextNodes and recognized types (string, SubString, primitives, arrays, enumerations).
    /// </summary>
    public class TextGenerator : TextReader {

        /// <summary>
        /// A convenience method to evaluate a node on a new context. 
        /// </summary>
        /// <param name="root">The root of the tree to evaluate.</param>
        /// <returns>The string result of evaluating the tree.</returns>
        public static string ReadToEnd(object root) {
            return new TextGenerator(root).ReadToEnd();
        }

        private TextNodeStack m_stack;
        private TextNodeTraversal m_traversal;
        private TextGeneratorState m_state;
        private IEnumerator<char?> m_generator;
        private int? m_current;
        
        // a collection of sub-trees to be evaluated in a separate generator by separate thread
        private Queue<TextNodeTask> m_taskQueue;

        /// <summary>
        /// Create a new generator to evaluate a tree.
        /// </summary>
        /// <param name="root">The root of the tree to evaluate.</param>
        public TextGenerator(params object[] root) {
            Contract.Ensures(GetType().Assembly == Assembly.GetExecutingAssembly());

            m_stack = new TextNodeStack(this);
            m_state = new TextGeneratorState(this);

            Initialize(root);
        }
        internal TextGenerator(TextGenerator source, object root) {
            Contract.Ensures(GetType().Assembly == Assembly.GetExecutingAssembly());

            m_state = source.m_state.DeepCopy(this);
            m_stack = source.m_stack.DeepCopy(this);

            Initialize(root);
        }
        private void Initialize(object root) {
            m_taskQueue = new Queue<TextNodeTask>();
            m_traversal = new TextNodeTraversal(this);

            m_stack.Push(Substitute(root));
        }

        internal TextGeneratorState State {
            get { return m_state; }
            set { m_state = value; }
        }
        internal TextNodeStack Stack {
            get { return m_stack; }
        }
        internal TextNodeTraversal Traversal {
            get { return m_traversal; }
        }

        internal object Substitute(object value) {
            if (value == null)
                return new object[0];

            if (Stack.Peek() != null) {

                // if markup is disabled then skip past the markup
                var info = TextNodeLoader.GetInfo(value);
                if (info.IsMarkup && State.IsMarkupTypeDisabled(info.MarkupType))
                    value = ((TextNode)value).MarkupContent() ?? new object[0];

                // see if any parent would like to substitute this child
                var substituteLink = Stack.Peek().SubtituteLink;
                if (substituteLink != null)
                    value = substituteLink.Substitute(this, value) ?? value;
            }

            // call ToString on those child type deemed primitive to save the hassle of having to substitute them
            if (TextNodeInfo.IsPrimitive(value)) {
                if (value is bool)
                    value = (bool)value ? "true" : "false";
                else
                    value = value.ToString();
            }

            return value;
        }
        internal virtual IEnumerable<char?> GetProducer(object value = null) {
            foreach (var character in Traversal.Traverse(value)) {
                if (character != null)
                    m_state.OnCharacterReturned((char)character);
                yield return character;
            }
        }
        internal void Fork(params object[] root) {
            Contract.Assert(!Traversal.FlatteningTraversal);

            if (State.ContentTraversal)
                return;

            if (State.EvaluateTraversal)
                return;

            var task = new TextNodeTask(this, root);
            m_taskQueue.Enqueue(task);
        }

        public TextNodeTask NextTask() {
            Peek();

            if (m_taskQueue.Count == 0)
                return null;

            return m_taskQueue.Dequeue();
        }

        public override int Peek() {
            if (m_generator == null)
                m_generator = GetProducer().GetEnumerator();

            if (m_current != null)
                return (int)m_current;

            while (m_current == null)
                m_current = m_generator.MoveNext() ? (int?)m_generator.Current : -1;

            return (int)m_current;
        }
        public override int Read(char[] buffer, int index, int count) {
            Contract.Requires(buffer != null);
            Contract.Requires(index >= 0);
            Contract.Requires(count >= 0);
            Contract.Requires(buffer.Length - index >= count);
            Contract.Ensures(Contract.Result<int>() >= 0);
            Contract.Ensures(Contract.Result<int>() <= Contract.OldValue(count));
            Contract.EndContractBlock();

            // initialize number of characters returned
            int result = 0;

            // initialize enumerator and consume null characters
            Peek();

            while (true) {

                // break if no more characters or if null (flush) is encountered
                if (m_current == null || (int)m_current == -1) 
                    break;

                // consume character
                buffer[index + result++] = (char)m_current;
                m_current = null;

                // break if the buffer is full or a new line is read
                if (result == count || State.AtEndOfNewLine)
                    break;
            
                // generate next character
                if (m_generator.MoveNext())
                    m_current = m_generator.Current;
            }

            return result;
        }
        public override int Read() {
            var result = Peek();
            if (result != -1)
                m_current = null;
            return result;
        }
    }

    public sealed class TextNodeTask : TextGenerator {

        private Thread m_thread;
        private Task m_task;
        private BlockingCollection<char?> m_blockingQueue;

        internal TextNodeTask(TextGenerator generator, object root)
            : base(generator, root) {

            m_blockingQueue = new BlockingCollection<char?>(1);
            m_task = new Task(TaskThreadStart);
        }

        private void TaskThreadStart() {
            m_thread = Thread.CurrentThread;

            foreach (var o in base.GetProducer())
                m_blockingQueue.Add(o);
            m_blockingQueue.CompleteAdding();
        }

        internal sealed override IEnumerable<char?> GetProducer(object value = null) {
            Contract.Ensures(m_task.Status == TaskStatus.Created);

            m_task.Start();
            foreach (var o in m_blockingQueue.GetConsumingEnumerable())
                yield return o;
        }

        public Task Task {
            get { return m_task; }
        }
    }

    /// <summary>
    /// The base class of types which are nodes in tree. Sub-classes must be immutable after construction
    /// and should lazily generate their children whenever possible. Virtual methods allow substituting 
    /// leafs (characters) and children generated during the post-order traversal of the tree.
    /// </summary>
    public abstract class TextNode {

        private bool m_hasConent;

        internal bool HasContent {
            get { 
                return m_hasConent; 
            }
            set {
                // can only set to true
                if (!value) 
                    throw new ArgumentException();

                m_hasConent = value; 
            }
        }

        /// <summary>
        /// Return to flush any buffered content out of the TextGenerator. 
        /// </summary>
        public static readonly object FlushContent = new TextFlush();

        /// <summary>
        /// A convenience value which can be returned by an override of Content() to indicate this node 
        /// considers itself to have content.
        /// </summary>
        public static readonly IEnumerable<object> ArbitraryContent = new[] { " " };
        public static readonly IEnumerable<object> EmptyContent = new object[] { };

        /// <summary>
        /// Called when a character is generated during evaluation of the sub tree rooted at this node providing
        /// an oppertunity to substitute the character with a string.
        /// </summary>
        /// <param name="context">The current state of the post-order traversal.</param>
        /// <param name="character">The character to escape.</param>
        /// <returns>Return null if the character is not escaped or a string to be used in place of the character.</returns>
        protected internal virtual string Escape(TextNodeContext context, char character) {
            return null;
        }

        /// <summary>
        /// Called when a non-character, non-string child is generated during evaluation of the sub tree rooted at this 
        /// node providing an oppertunity to substitute the object with another object. TextNodeSubstituteTargetAttribute
        /// allows filtering which types of children are candidates for substitution when applied to an override of this method.
        /// </summary>
        /// <param name="context">The current state of the post-order traversal. Note that 'value' has not yet been pushed 
        /// onto the stack and so not accessable from the context.</param>
        /// <param name="value">A child generated during the post-order walk.</param>
        /// <returns>Return null if the value should not be substituted (the same as simply returning the value)
        /// or an object to substitute for the value.</returns>
        protected internal virtual IEnumerable<object> Substitute(TextNodeContext context, object value) {
            return null;
        }

        /// <summary>
        /// Called during the post-order tree traversal to generate children of this node. TextNodeAlwaysHasContentAttribute
        /// can be applied to overrides of this method to indicate that this node always has content.  
        /// </summary>
        /// <param name="context">The current state of the post-order traversal.</param>
        /// <returns>Children of this node.</returns>
        protected internal virtual IEnumerable<object> Children(TextNodeContext context) {
            return null;
        }

        /// <summary>
        /// Parent nodes can call context.ContainsContent() to determin if this node considers itself to have
        /// "content". By default this method calls Children but can be overriden to provide an optimized or 
        /// custom semantic for whether or not this node contains content. For example, Children() for an xml 
        /// comment would return <!-- and --> but it's Content() would only return the actual text of the comment.
        /// </summary>
        /// <param name="context">The current state of the post-order traversal.</param>
        /// <returns>Children that contain "content" for this node.</returns>
        protected internal virtual IEnumerable<object> Content() {
            throw new InvalidOperationException();
        }

        /// <summary>
        /// Invoked before the TextNode is pushed onto the stack. Stateful TextNodes must override 
        /// Prolog and re-initialize themself so they could be pushed onto the stack again.
        /// </summary>
        /// <param name="context">The context just before this TextNode is pushed onto the stack.</param>
        protected internal virtual void Prolog(TextNodeContext context) {
        }

        /// <summary>
        /// Invoked just after the TextNode is popped off the stack. Stateful TextNodes must override 
        /// Prolog and cleanup\commit themself.
        /// </summary>
        /// <param name="context">The context just before this TextNode is pushed onto the stack.</param>
        protected internal virtual void Epilog(TextNodeContext context) {
        }

        /// <summary>
        /// Returns un-marked up content in a markup TextNode. For example, the text inside
        /// a xml Element, CData, or Text node. Can only override if attribted with 
        /// TextNodeMarkupAttribute.
        /// </summary>
        protected internal virtual IEnumerable<object> MarkupContent() {
            return null;
        }

        /// <summary>
        /// The string result of evaluating tree rooted at this node.
        /// </summary>
        /// <returns>The value of new TextGenerator(this).ReadToEnd();</returns>
        public string ReadToEnd() {
            return ToTextReader().ReadToEnd();
        }

        /// <summary>
        /// Return a TextReader that will lazily generate a string from 
        /// the tree rooted as this node.
        /// </summary>
        /// <returns>The value of new TextGenerator(this);</returns>
        public TextReader ToTextReader() {
            return new TextGenerator(this);
        }
    }

    /// <summary>
    /// Apply to a TextNode class to filter the type of children passed to TextNode.Substitute().
    /// </summary>
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Struct)]
    public sealed class TextNodeSubstituteTargetsAttribute : Attribute {

        private Type[] m_types;

        /// <summary>
        /// List of types which a child must be assignable to inorder to be passed to TextNode.Substitute().
        /// </summary>
        /// <param name="types"></param>
        public TextNodeSubstituteTargetsAttribute(params Type[] types) {
            m_types = types;
        }

        /// <summary>
        /// List of types which a child must be assignable to inorder to be passed to TextNode.Substitute().
        /// </summary>
        public Type[] Types() {
            return m_types;
        }
    }

    /// <summary>
    /// Apply to a TextNode class to filter the set of characters passed to TextNode.Escape().
    /// </summary>
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Struct)]
    public sealed class TextNodeEscapeTargetsAttribute : Attribute {

        private char[] m_characters;

        /// <summary>
        /// Apply to a TextNode class to filter the set of characters passed to TextNode.Escape().
        /// </summary>
        /// <param name="types">Filter set of characters be passed to TextNode.Escape().</param>
        public TextNodeEscapeTargetsAttribute(params char[] characters) {
            m_characters = characters;
        }

        /// <summary>
        /// Filter set of characters be passed to TextNode.Escape().
        /// </summary>
        public char[] Characters() {
            return m_characters;
        }
    }

    /// <summary>
    /// Apply to a TextNode to indicate that all its subclasses mark the start of markup. 
    /// The end of markup is marked by a subclass that is attributed with TextNodeEndMarkupAttribute.
    /// </summary>
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Struct)]
    public sealed class TextNodeMarkupAttribute : Attribute {
    }

    /// <summary>
    /// Apply to a TextNode to indicate it marks the end of markup. Must be applied to 
    /// subclass that is attributed with TextNodeMarkupAttribute inorder to tell what
    /// markup type is ending.
    /// </summary>
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Struct)]
    public sealed class TextNodeEndMarkupAttribute : Attribute {
    }

    /// <summary>
    /// The node always has content. Applying this to a TextNode has the same effect 
    /// as overriding TextNode.Content() to always return content. Similarly, ff a derived 
    /// class overrides TextNode.Content() then inherited applications of this attribute 
    /// are ignored.
    /// </summary>
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Struct)]
    public sealed class TextNodeContainsContentAttribute : Attribute {
    }

    /// <summary>
    /// Indicates the TextNode node maintains state and so only one refrence to an instance
    /// should exist in any stack at any time. Stateful TextNodes must be decorated 
    /// TextNodeHasSideEffectAttribute and must override Prolog to (re)initialize itself 
    /// when pushed onto the stack and Epilog to cleanup\commit itself when popped off the stack. 
    /// </summary>
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Struct)]
    public sealed class TextNodeContainsStateAttribute : Attribute {
    }

    /// <summary>
    /// The node has a side effect other than producing text. To prevent calling Children 
    /// twice during a single traversal a runtime exception will be thrown if the TextNode 
    /// is part of a ContainsContent and Content is not overriden or if it is part of an 
    /// Evaluate traversal. 
    /// </summary>
    [AttributeUsage(AttributeTargets.Class | AttributeTargets.Struct)]
    public sealed class TextNodeHasSideEffectAttribute : Attribute {
    }

    public class TextNodes<T> : TextNode, IEnumerable<T> {

        private List<T> m_objects;

        public TextNodes() {
            m_objects = new List<T>();
        }

        protected internal IEnumerable<T> Children() {
            return m_objects;
        }
        protected internal override IEnumerable<object> Children(TextNodeContext context) {
            return Children().Cast<object>();
        }
        protected internal override IEnumerable<object> Content() {
            return Children().Cast<object>();
        }

        public void Add(T element) {
            m_objects.Add(element);
        }
        IEnumerator<T> IEnumerable<T>.GetEnumerator() {
            throw new NotSupportedException("TextNodes can only be enumerated during a traversal by TextGenerator.");
        }
        IEnumerator IEnumerable.GetEnumerator() {
            throw new NotSupportedException("TextNodes can only be enumerated during a traversal by TextGenerator.");
        }
    }

    public class TextNodes : TextNodes<object> {
    }

    [TextNodeContainsContent]
    public sealed class TextFlush : TextNode {
    }
}
